\section{Previous work}

\subsection{Overview of existing techniques}

In his excellent paper describing how \sbcl{} is bootstrapped
\cite{Rhodes:2008:SSC:1482373.1482380}, Rhodes gives an overview of
how different existing \commonlisp{} systems are made to evolve.
Below, we summarize the contents of that paper.

We can divide \commonlisp{} implementations into those that are mostly
written in some other language, and those that are mostly written in
\commonlisp{}.

In the first category, there are implementations that specifically
cater to applications written in that other language and that need
some scripting capabilities that are supplied by the \commonlisp{}
implementation.  Whether it is advantageous or not for these
implementations to be written mainly in that other language is outside
the scope of this paper.

Of the implementations in the second category that are currently
actively used, Rhodes claims%
\footnote{For the commercial \commonlisp{} implementations cited in
  the paper by Rhodes, he includes a disclaimer that only anecdotal
  evidence for this information is available.}
that \allegro{}, \lispworks{}, \cmucl{}, Scieneer, and \ccl{} are only
possible to build using older versions of the same system, and only
using image-based techniques.  Only \sbcl{} can be bootstrapped using
several other \commonlisp{} implementations.

Even a \commonlisp{} implementation that is largely written in
\commonlisp{} such as \sbcl{} has some amount of code written in other
languages.  In the case of \sbcl{}, Rhodes gives the number
$35\thinspace000$ lines of \clanguage{} and assembly code ``for
services such as signal handling and garbage collection'', of which
$8\thinspace000$ is for the garbage collector.  The remaining lines
can be summarized as around $2\thinspace000$ lines per operating
system supported.  This is a very modest amount of code written in
other languages.

\subsection{\commonlisp{} systems in other languages}

When a language such as \clanguage{} or \cplusplus{} is used to
implement a \commonlisp{} system, a small subset of the \commonlisp{}
language is implemented this way.  We call that subset the \emph{base}
language.  The result of the initial bootstrapping procedure is
typically an executable file containing the base system.  Additional
modules are then added to the base system to obtain a complete
\commonlisp{} system.  These additional modules must be implemented in
the subset of \commonlisp{} defined by the base language and
previously added modules.

There are several issues with this technique.  For one thing, some
major components that would be more easily expressed in \commonlisp{}
must be written using the implementation language so that new modules
can be added to the system, in particular a reader and an evaluator.

Another major issue has to do with maintenance.  When one of the
additional modules is modified, it is easy to forget exactly what
subset of the \commonlisp{} language is allowed at that point in the
bootstrapping procedure.  The code for a particular module must often be
expressed in some unidiomatic way and it is tempting to make the
modified code more idiomatic, but doing so will then break the
bootstrapping procedure.

\subsection{\commonlisp{} systems in \commonlisp{}}
\label{sec-cl-in-cl}

Because of the way compilation is defined by the \commonlisp{}
standard, there are some issues that need to be resolved in order for
it to be possible for a target \commonlisp{} system to be bootstrapped
on a host \commonlisp{} system.  Since \sbcl{} is very likely the only
\commonlisp{} implementation written mostly in \commonlisp{} that can
be built from an existing \commonlisp{} implementation, we describe
how \sbcl{} solves some of these issues.

\subsubsection{Packages and environments}

Most existing \commonlisp{} systems have a single global environment
that is used both as the compilation environment and as the run-time
environment.  Compiling \commonlisp{} source code requires the
existence of definitions of macros, types, etc. in that environment,
and when source code for a target \commonlisp{} system is compiled
using a host \commonlisp{} system, these definitions must be those of
the target system.  However, with a single global environment there
can only be one definition of these entities.

\sbcl{} solves this problem by using different package names for the
code of the host system and the target system.  In a final step, the
packages of the target system are then renamed to conform to the
standard.

\subsubsection{The compiler and \clos{}}

Some aspects of \clos{} require the presence of the compiler, at least
if the resulting code is required to have some reasonable
performance.  In particular, the compiler is required to create a
discriminating function from the effective methods%
\footnote{Recall that the result of a call to
  \texttt{compute\--effective\--method} is a lambda expression.  This
  lambda expression must be turned into something that is executable,
  hence the need for an evaluator.}
returned by \texttt{compute\--effective\--method}.
For that reason, it becomes difficult to use generic
functions and standard classes in the code of the compiler itself.

\sbcl{} solves this issue by not using generic functions and standard
classes in the code of the compiler.  Thus, \sbcl{} can load the
compiler into a minimal running target system and then bootstrap
\clos{} afterwards.

However, not using generic functions and standard classes in the
compiler has some of the same problems as \commonlisp{} systems that
are written in some other language, namely that care has to be taken
to make sure the proper subset of the language is used when the code
of the compiler is being worked on.  Furthermore, generic functions
and standard classes are great tools for structuring complex code, so
not being able to use these tools in such a significant and complex
part of a \commonlisp{} implementation negatively affects the clarity
and maintainability of the code.
